/**
 * 二分查找
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
export var maxDistance = function (nums1, nums2) {
  // 先找出有效的下标对
  let ans = 0
  for (let i = 0; i < nums1.length; i++) {
    const j = bisect(nums2, nums1[i])
    if (j === -1 || i > j) continue
    ans = Math.max(ans, j - i)
  }
  return ans
}

function bisect(nums, target) {
  let left = 0
  let right = nums.length - 1
  let ans = -1
  while (left <= right) {
    const mid = Math.floor((left + right) / 2)
    if (nums[mid] >= target) {
      ans = mid
      left = mid + 1
    } else {
      right = mid - 1
    }
  }
  return ans
}

/**
 * 双指针
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
export var maxDistance2 = function (nums1, nums2) {
  let i = 0,
    j = 0,
    ans = 0
  while (i < nums1.length) {
    while (j < nums2.length && nums1[i] <= nums2[j]) {
      j++
    }
    ans = Math.max(ans, j - i - 1)
    i++
    // j = Math.max(j, i)
  }
  return ans
}
